package newcoder_exp.justPractise;

import org.junit.Test;

import linked.ListNode;

public class NC2 {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        ListNode h1 = head, p = h1;
        ListNode h2 = head.next, q = h2;
        q = p;
        ListNode cur = h2.next;
        ListNode temp = null, temp2 = null;
        while (q != null && q.next != null) {
            temp = p;
            p = p.next;
            q = q.next.next;
        }
        if (q == null) {
            h2 = p.next;
            p.next = null;
        } else {
            h2 = p;
            temp.next = null;
        }
        h2 = reverse(h2);
        head = h1;
         while (h1 != null && h2 != null) {
            temp = h1.next;
            temp2 = h2.next;
            h2.next = h1.next;
            h1.next = h2;
            h1 = temp;
            h2 = temp2;
        }
        if (temp2 != null) {
            h1 = head;
            while (h1.next != null) h1 = h1.next;
            h1.next = temp2;
        }
    }

    public ListNode reverse(ListNode head) {
        ListNode pre = null, post = head, temp;
        while (post != null) {
            temp = post.next;
            post.next = pre;
            pre = post;
            post = temp;
        }  
        return pre;
    }

    @Test
    public void test() {
        int[] nums = new int[]{1,2,3,4,5,6};
        ListNode head = ListNode.newListNodeFromArray(nums);
        
        reorderList(head);
        System.out.println(head);
    }
}
